// 2025/3/29
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
// 买卖股票的最佳时机4

class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            int n = prices.size();
            vector<int> dp(2 * k, 0);
            for(int j = 0; j < 2 * k; j += 2)
                dp[j] = -prices[0];
    
            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < 2 * k; j += 2)
                {
                    if(j == 0) dp[j] = max(dp[j], -prices[i]);
                    else dp[j] = max(dp[j], dp[j - 1] - prices[i]);
    
                    dp[j + 1] = max(dp[j + 1], dp[j] + prices[i]);
                }
            }
            return dp[2 * k - 1];
        }
    };